Search for: All records

Probabilistic zero forcing is a graph coloring process in which blue vertices infect (color blue) white vertices with a probability proportional to the number of neighboring blue vertices. This paper introduces reversion probabilistic zero forcing (RPZF), which shares the same infection dynamics but also allows for blue vertices to revert to being white in each round. A threshold number of blue vertices is produced such that the complete graph is entirely blue in the next round of RPZF with high probability. Utilizing Markov chain theory, a tool is formulated which, given a graph's RPZF Markov transition matrix, calculates the probability of whether the graph becomes all white or all blue as well as the time at which this is expected to occur. 

A sign pattern is an array with entries in $$\{+,-,0\}$$. A real matrix $$Q$$ is row orthogonal if $QQ^T = I$. The Strong Inner Product Property (SIPP), introduced in [B.A. Curtis and B.L. Shader, Sign patterns of orthogonal matrices and the strong inner product property, Linear Algebra Appl. 592: 228-259, 2020], is an important tool when determining whether a sign pattern allows row orthogonality because it guarantees there is a nearby matrix with the same property, allowing zero entries to be perturbed to nonzero entries, while preserving the sign of every nonzero entry. This paper uses the SIPP to initiate the study of conditions under which random sign patterns allow row orthogonality with high probability. Building on prior work, $$5\times n$$ nowhere zero sign patterns that minimally allow orthogonality are determined. Conditions on zero entries in a sign pattern are established that guarantee any row orthogonal matrix with such a sign pattern has the SIPP.